package com.github.tangmonkmeat;

/**
 * Description:
 *
 * @author zwl
 * @version 1.0
 * @date 2021/6/30 下午3:13
 */
public class 零钱兑换2 {

    public static void main(String[] args) {
        int change = new 零钱兑换2().change(5, new int[]{1, 2, 5});
        System.out.println(change);
    }

    public int change2(int amount,int[] coins){
        //递推表达式
        int[] dp = new int[amount + 1];
        //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0] = 1;
        // 假设 只有
        for (int coin : coins) {
            for (int j = coin; j <= amount; j++) {
                dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }

    int res = 0;

    public int change(int amount, int[] coins) {
        //
        dp(amount,coins,amount,coins.length - 1);
        return res;
    }

    public void dp(int amount, int[] coins, int has,int index){
        if(has == 0){
            res++;
            return;
        }
        // 不符合，下一个
        if(has < 0){
            return;
        }

        for(int i = index; i >= 0; i--){
            int j = has / coins[i];
            dp(amount,coins, has - j * coins[i], i - 1);
        }
    }

}
